//返回前k个高频次出现的元素
//使用unordered_map和优先队列来实现
//映射可以存放元素和其出现频率
//优先队列维护最大或最小的元素在队列前面，相当于一个堆
#include <unordered_map>
#include <vector>
#include <queue> 
using std::vector;           
using std::priority_queue;      //优先队列在队列里面
using std::pair;
using std::unordered_map;
            //自定义比较器，默认是大顶堆
struct mycomparsion{
    bool operator()(pair<int,int>& lhs,pair<int,int>&rhs){
        return lhs.second>rhs.second;   //>是小顶堆，<是大顶堆
    }
};//    小顶堆
vector<int> topKFrequent(vector<int>& nums, int k){
    unordered_map<int,int> map;
    priority_queue<pair<int,int>,vector<pair<int,int>>,mycomparsion> pri_que;
    //三个参数  ： 存放内容         容器(默认vector)                比较器（接受的是类或者结构）
        //map里面单个元素都是pair
    for(int i:nums)
        map[i]++;
    
    //维护最大的都在下面，大于k将堆顶弹出，弹出的是最小的
    for(unordered_map<int,int>::iterator it=map.begin();it!=map.end();it++){
        pri_que.push(*it);
        if(pri_que.size()>k)
            pri_que.pop();
    }
    vector<int> res(k);
    for(int i=0;i<k;i++){
        res[i]=pri_que.top().first;
        pri_que.pop();
    }
    return res;

}